{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find K-th Smallest Pair Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestDistancePair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出第 K 小的数对距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>数对 <code>(a,b)</code> 由整数 <code>a</code> 和 <code>b</code> 组成，其数对距离定义为 <code>a</code> 和 <code>b</code> 的绝对差值。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，数对由 <code>nums[i]</code> 和 <code>nums[j]</code> 组成且满足 <code>0 &lt;= i &lt; j &lt; nums.length</code> 。返回 <strong>所有数对距离中</strong> 第 <code>k</code> 小的数对距离。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,1], k = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数对和对应的距离如下：\n",
    "(1,3) -&gt; 2\n",
    "(1,1) -&gt; 0\n",
    "(3,1) -&gt; 2\n",
    "距离第 1 小的数对是 (1,1) ，距离为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1], k = 2\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,6,1], k = 3\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n * (n - 1) / 2</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-k-th-smallest-pair-distance](https://leetcode.cn/problems/find-k-th-smallest-pair-distance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-k-th-smallest-pair-distance](https://leetcode.cn/problems/find-k-th-smallest-pair-distance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,1]\\n1', '[1,1,1]\\n2', '[1,6,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def possible(guess: int) -> bool:\n",
    "            count = 0\n",
    "            left = 0\n",
    "            for i in range(n):\n",
    "                while left < i and nums[i] - nums[left] > guess:\n",
    "                    left += 1\n",
    "                count += i - left\n",
    "            \n",
    "            return count >= k\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if possible(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "            \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_cnt(mid):\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > mid:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if get_cnt(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right, ans = 0, 0, 0\n",
    "        # limit想尽量小！\n",
    "        right=nums[-1]-nums[0]\n",
    "        while left <= right:\n",
    "            mid = left+((right-left) >> 1)\n",
    "            if self.f(nums, mid) < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                ans = mid\n",
    "                right = mid-1\n",
    "        return ans\n",
    "\n",
    "    # 返回差值<=limit的数对有多少\n",
    "    def f(self, nums: List[int], limit: int):\n",
    "        ans, L, R = 0, 0, 0\n",
    "        N = len(nums)\n",
    "        while L < N-1:\n",
    "            while R < N-1 and nums[R+1]-nums[L] <= limit:\n",
    "                R += 1\n",
    "            ans += (R-L)\n",
    "            L += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        start = ans = 0\n",
    "        end = nums[-1] - nums[0]\n",
    "\n",
    "        while start <= end:\n",
    "            mid = (start + end) // 2\n",
    "\n",
    "            c = 0\n",
    "            for i in range(n-1):\n",
    "                l,r = i+1,n-1\n",
    "                t,ind = nums[i],i\n",
    "                while l <= r:\n",
    "                    m = (l + r) // 2\n",
    "                    if nums[m] - t <= mid:\n",
    "                        ind = m\n",
    "                        l = m + 1\n",
    "                    else:\n",
    "                        r = m - 1\n",
    "\n",
    "                c += ind - i\n",
    "                if c >= k:\n",
    "                    break\n",
    "\n",
    "            if c < k:\n",
    "                start = mid + 1\n",
    "                \n",
    "            else:\n",
    "                ans = mid\n",
    "                end = mid - 1                \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            for j, num in enumerate(nums):\n",
    "                i = bisect_left(nums, num - mid, 0, j)\n",
    "                cnt += j - i\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        return bisect_left(range(nums[-1] - nums[0]), k, key=count)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right, ans = 0, 0, 0\n",
    "        # limit想尽量小！\n",
    "        right=nums[-1]-nums[0]\n",
    "        while left <= right:\n",
    "            mid = left+((right-left) >> 1)\n",
    "            if self.f(nums, mid) < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                ans = mid\n",
    "                right = mid-1\n",
    "        return ans\n",
    "\n",
    "    # 返回差值<=limit的数对有多少\n",
    "    def f(self, nums: List[int], limit: int):\n",
    "        ans, L, R = 0, 0, 0\n",
    "        N = len(nums)\n",
    "        while L < N-1:\n",
    "            while R < N-1 and nums[R+1]-nums[L] <= limit:\n",
    "                R += 1\n",
    "            ans += (R-L)\n",
    "            L += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def countLessEquals(nums: List[int], threshold: int) -> int:\n",
    "            count = 0\n",
    "            left, right = 0, 0\n",
    "            while right < len(nums):\n",
    "                while nums[right] - nums[left] > threshold:\n",
    "                    left +=1\n",
    "                count += right - left\n",
    "                right +=1\n",
    "            return count\n",
    "\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            count = countLessEquals(nums, mid) #统计距离小于等于 mid 的距离对数\n",
    "            if count < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        dist = nums[-1] - nums[0]\n",
    "\n",
    "        def count(d):\n",
    "            total = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                j = bisect.bisect_left(nums, num - d)\n",
    "                total += i - j\n",
    "            return total\n",
    "        \n",
    "        ans = bisect.bisect_left(range(dist), k, key=count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        def check(mid):\n",
    "            i = 0\n",
    "            tot = 0\n",
    "            for j, x in enumerate(nums):\n",
    "                while x - nums[i] > mid:\n",
    "                    i += 1\n",
    "                tot += j - i\n",
    "            return tot < k\n",
    "        \n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "                \n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            left, count = 0, 0\n",
    "            for right in range(1, len(nums)):\n",
    "                while nums[right] - nums[left] > dis:\n",
    "                    left += 1\n",
    "                count += (right - left)\n",
    "            return count\n",
    "\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if get_count(mid) < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        import bisect\n",
    "        nums.sort()\n",
    "        def count(diff):\n",
    "            cnt = 0\n",
    "            for i,num in enumerate(nums):\n",
    "                j = bisect.bisect_right(nums[i+1:],num+diff)\n",
    "                cnt += j\n",
    "            #print(diff,cnt)\n",
    "            return cnt\n",
    "        return bisect.bisect_left(range(nums[-1]-nums[0]),k,key=count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > dis:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "        \n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if get_count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        def count(mid):\n",
    "            cnt = 0\n",
    "            l = 0\n",
    "            for r in range(n):\n",
    "                while abs(nums[r] - nums[l]) > mid:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "\n",
    "        while left < right:\n",
    "            mid = (right + left) // 2\n",
    "            if count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        def count_pairs(distance, nums):\n",
    "            total = 0\n",
    "            left = 0\n",
    "            n = len(nums)\n",
    "            for i in range(n):\n",
    "                while nums[i] - nums[left] > distance:\n",
    "                    left += 1\n",
    "                total += i-left\n",
    "            return total\n",
    "\n",
    "        left, right = 0, nums[-1]-nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if count_pairs(mid,nums) < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dist):\n",
    "            left, count = 0, 0\n",
    "            for right in range(1, len(nums)):\n",
    "                while nums[right] - nums[left] > dist:\n",
    "                    left += 1\n",
    "                count += (right - left)\n",
    "            return count\n",
    "\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if get_count(mid) >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def woo(n):\n",
    "            res = 0\n",
    "            i = 0\n",
    "            for j in range(1, len(nums)):\n",
    "                while nums[j]-nums[i]>n:\n",
    "                    i += 1\n",
    "\n",
    "                res += j-i\n",
    "            return res\n",
    "\n",
    "        l = 0\n",
    "        r = nums[-1]-nums[0]\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            cnt = woo(mid)\n",
    "            if cnt<k:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def check(nums, limit):\n",
    "            l = 0\n",
    "            r = 0\n",
    "            cnt = 0\n",
    "            while l < len(nums):\n",
    "                while r + 1 < len(nums):\n",
    "                    if nums[r+1] - nums[l] <= limit:\n",
    "                        r += 1\n",
    "                    else:\n",
    "                        break\n",
    "                cnt += r - l\n",
    "                l += 1\n",
    "            return cnt\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = nums[-1] - nums[0]\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(nums, mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        start = ans = 0\n",
    "        end = nums[-1] - nums[0]\n",
    "\n",
    "        while start <= end:\n",
    "            mid = (start + end) // 2\n",
    "\n",
    "            c = 0\n",
    "            for i in range(n-1):\n",
    "            #     j = i\n",
    "            #     while (j+1 < n and nums[j+1] - nums[i] <= mid):\n",
    "            #         j += 1\n",
    "            #     c += j - i\n",
    "                l,r = i+1,n-1\n",
    "                t,ind = nums[i],i\n",
    "                while l <= r:\n",
    "                    m = (l + r) // 2\n",
    "                    if nums[m] - t <= mid:\n",
    "                        ind = m\n",
    "                        l = m + 1\n",
    "                    else:\n",
    "                        r = m - 1\n",
    "\n",
    "                c += ind - i\n",
    "                if c >= k:\n",
    "                    break\n",
    "\n",
    "            if c < k:\n",
    "                start = mid + 1\n",
    "                \n",
    "            else:\n",
    "                ans = mid\n",
    "                end = mid - 1                \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            for j, num in enumerate(nums):\n",
    "                i = bisect_left(nums, num - mid, 0, j)\n",
    "                cnt += j - i\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        # 使用二分查找找到满足 count(mid) >= k 的最小的 mid 值\n",
    "        return bisect_left(range(nums[-1] - nums[0]), k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_cnt(mid):\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > mid:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if get_cnt(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            cnt = 0\n",
    "            l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while (nums[r]-nums[l]) > dis:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "        \n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            if get_count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: list[int], k: int) -> int:\n",
    "        @cache\n",
    "        def count(distance):\n",
    "            sum_ = 0\n",
    "            for right in range(1, len(nums)):\n",
    "                lo_ = 0\n",
    "                hi_ = right\n",
    "                while lo_ < hi_:\n",
    "                    mid_ = lo_ + hi_ >> 1\n",
    "                    if nums[right] - nums[mid_] <= distance:\n",
    "                        hi_ = mid_\n",
    "                    else:\n",
    "                        lo_ = mid_ + 1\n",
    "                sum_ += (right - lo_)\n",
    "            return sum_\n",
    "\n",
    "        nums.sort()\n",
    "        lo = 0\n",
    "        hi = nums[-1] - nums[0]\n",
    "        while lo < hi:\n",
    "            mid = lo + hi >> 1\n",
    "            if count(mid) >= k:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        @cache\n",
    "        def count(d):\n",
    "            count = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                j = bisect_left(nums, num - d, 0, i)\n",
    "                count += i - j\n",
    "            return count\n",
    "        \n",
    "        ans = bisect_left(range(nums[-1] - nums[0]), k, key=count)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right, ans = 0, 0, 0\n",
    "        # limit想尽量小！\n",
    "        right=nums[-1]-nums[0]\n",
    "        while left <= right:\n",
    "            mid = left+((right-left) >> 1)\n",
    "            if self.f(nums, mid) <= k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                ans = mid\n",
    "                right = mid-1\n",
    "        return ans\n",
    "\n",
    "    # 返回差值limit的数对是第几小\n",
    "    # 计算以每个数开头的有几个\n",
    "    def f(self, nums: List[int], limit: int):\n",
    "        ans, L, R = 0, 0, 0\n",
    "        N = len(nums)\n",
    "        while L < N-1:\n",
    "            while R < N-1 and nums[R+1]-nums[L] <= limit:\n",
    "                R += 1\n",
    "            ans += (R-L)\n",
    "            L += 1\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 首先对数组进行排序\n",
    "\n",
    "\n",
    "        def count_pairs(diff):\n",
    "            count = 0\n",
    "            left = 0\n",
    "            for right in range(len(nums)):\n",
    "                while nums[right] - nums[left] > diff:\n",
    "                    left += 1\n",
    "                count += right - left\n",
    "            return count\n",
    "        left = 0\n",
    "        right = max(nums) - min(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if count_pairs(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def check(d):\n",
    "            cnt = left = 0\n",
    "            for right in range(1, n):\n",
    "                while left < right and nums[right]-nums[left] > d:\n",
    "                    left += 1\n",
    "                if nums[right]-nums[left] <= d:\n",
    "                    cnt += right-left\n",
    "                    if cnt >= k:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l, r = 0, nums[-1]-nums[0]\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if check(m): # 距离m，找不到k个对\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > dis:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "        # def get_cnt(dis):\n",
    "        #     cnt = 0\n",
    "        #     for i in range(len(nums) - 1):\n",
    "        #         left, right =i, len(nums) - 1\n",
    "        #         while right > left:\n",
    "        #             if nums[right] - nums[left] > dis:\n",
    "        #                 right -= 1\n",
    "        #             else:\n",
    "        #                 break\n",
    "        #         cnt += right - left\n",
    "        #     return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        min_dis, max_dis = 0, nums[-1] - nums[0]\n",
    "\n",
    "        while max_dis > min_dis:\n",
    "            mid_dis = (max_dis + min_dis) // 2\n",
    "\n",
    "            count = get_count(mid_dis)\n",
    "            if count < k:\n",
    "                min_dis = mid_dis + 1\n",
    "            else:\n",
    "                max_dis = mid_dis\n",
    "\n",
    "        return min_dis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        # 暴力遍历，超时\n",
    "        n = len(nums)\n",
    "        distance = []\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1, n):\n",
    "                tmp = abs(nums[i]-nums[j])\n",
    "                distance.append(tmp)\n",
    "        distance.sort()\n",
    "        return distance[k-1]\n",
    "        '''\n",
    "\n",
    "        # 二分法\n",
    "        def count(partition): # 统计差值小于等于partition的对数\n",
    "            left, right = 0, 0\n",
    "            n = len(nums)\n",
    "            cnt = 0\n",
    "            # 用滑动窗口计算数量\n",
    "            while right < n:\n",
    "                while left < n and nums[right] - nums[left] > partition:\n",
    "                    left += 1\n",
    "                cnt += (right - left)\n",
    "                right += 1\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        right = nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            tmp = count(mid)\n",
    "            if tmp < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    mid = distance\n",
    "    left = 0\n",
    "    right = largest - smallest\n",
    "    situation 1: if mid is smaller than target, mid is the pth smallest, while p < k \n",
    "    situation 2: if mid is bigger than target, mid is the pth smallest, while p > k \n",
    "    how to find p?\n",
    "    for each number in nums, find how many numbers are <= nums[i] - mid \n",
    "    '''\n",
    "    '''\n",
    "    [1, 3, 2, 4, 1] k = 5 mid = 2\n",
    "    [1, 1, 2, 3, 4]\n",
    "                 i        \n",
    "           j  \n",
    "    i = 0, j = 0, 0\n",
    "    i = 1, j = 0, (1, 1)\n",
    "    i = 2, j = 0, (2, 1), (2, 1)\n",
    "    i = 3, j = 0, (3, 1), (3, 1), (3, 2)\n",
    "    i = 4, j = 2, (4, 2), (4, 3)\n",
    "    '''\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        left = 0 \n",
    "        right = nums[-1] - nums[0]\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2 \n",
    "\n",
    "            if self.enough(nums, k, mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "\n",
    "    def enough(self, nums, k, mid):\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            while nums[right] - nums[left] > mid:\n",
    "                left += 1\n",
    "            k -= right - left \n",
    "        return k <= 0  # p > k, mid is too big"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def smallestDistancePair(self, nums, k):\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        def count(mid):\n",
    "            right = 0\n",
    "            cnt = 0\n",
    "            for left in range(n):\n",
    "                while right < n and nums[right] - nums[left] <= mid:\n",
    "                    right += 1\n",
    "                    cnt += right - left - 1\n",
    "            return cnt\n",
    "\n",
    "        low = 0\n",
    "        upper = nums[-1] - nums[0]\n",
    "        while low < upper:\n",
    "            mid = (low + upper) // 2\n",
    "            r = count(mid)\n",
    "            if r >= k:\n",
    "                upper = mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "\n",
    "        return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        def count(x):\n",
    "            cnt = 0\n",
    "            for i, n in enumerate(nums):\n",
    "                cnt += i - bisect_left(nums, n-x, hi=i)\n",
    "            return cnt\n",
    "        return bisect_left(range(0, nums[-1]-nums[0]+1), k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            for j, num in enumerate(nums):\n",
    "                i = bisect_left(nums, num - mid, 0, j)\n",
    "                cnt += j - i\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        return bisect_left(range(nums[-1] - nums[0]), k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def count(d):\n",
    "            count = 0\n",
    "            j = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                while nums[j] < num - d:\n",
    "                    j += 1\n",
    "                count += i - j\n",
    "            return count\n",
    "        \n",
    "        ans = bisect_left(range(nums[-1] - nums[0]), k, key=count)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 首先对数组进行排序\n",
    "\n",
    "        def count_pairs(diff):\n",
    "            count = 0\n",
    "            left = 0\n",
    "            for right in range(len(nums)):\n",
    "                while nums[right] - nums[left] > diff:\n",
    "                    left += 1\n",
    "                count += right - left\n",
    "            return count\n",
    "\n",
    "        left = 0\n",
    "        right = max(nums) - min(nums)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if count_pairs(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > dis:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "        # def get_cnt(dis):\n",
    "        #     cnt = 0\n",
    "        #     for i in range(len(nums) - 1):\n",
    "        #         left, right =i, len(nums) - 1\n",
    "        #         while right > left:\n",
    "        #             if nums[right] - nums[left] > dis:\n",
    "        #                 right -= 1\n",
    "        #             else:\n",
    "        #                 break\n",
    "        #         cnt += right - left\n",
    "        #     return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        min_dis, max_dis = 0, nums[-1] - nums[0]\n",
    "\n",
    "        while max_dis > min_dis:\n",
    "            mid_dis = (max_dis + min_dis) // 2\n",
    "\n",
    "            count = get_count(mid_dis)\n",
    "            if count < k:\n",
    "                min_dis = mid_dis + 1\n",
    "            else:\n",
    "                max_dis = mid_dis\n",
    "\n",
    "        return min_dis\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        import bisect\n",
    "        nums.sort()\n",
    "        def count(diff):\n",
    "            cnt = 0\n",
    "            for i,num in enumerate(nums):\n",
    "                j = bisect.bisect_right(nums[i+1:],num+diff)\n",
    "                cnt += j\n",
    "            print(diff,cnt)\n",
    "            return cnt\n",
    "        return bisect.bisect_left(range(nums[-1]-nums[0]),k,key=count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            left = 0\n",
    "            count = 0\n",
    "            for right in range(1, len(nums)):\n",
    "                while nums[right] - nums[left] > dis:\n",
    "                    left += 1\n",
    "                count += (right - left)\n",
    "            return count\n",
    "        \n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if get_count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        right = max(nums) - min(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def get_left_pos(target, right):\n",
    "            left = 0\n",
    "            \n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            \n",
    "            return left\n",
    "\n",
    "        def check(dist):\n",
    "            ii = 0\n",
    "            ans = 0\n",
    "            for jj in range(1, len(nums)):\n",
    "                # while ii < jj and nums[jj] - nums[ii] < dist:\n",
    "                while nums[jj] - nums[ii] > dist:\n",
    "                    # ans += 1\n",
    "                    ii += 1\n",
    "                \n",
    "                ans += jj - ii\n",
    "            \n",
    "            return ans\n",
    "                \n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            current_cnt = check(mid)\n",
    "            # print(current_cnt, left, right)\n",
    "\n",
    "            if current_cnt < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "            \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        def check(dist):\n",
    "            cnt=0\n",
    "            for i,num in enumerate(nums):\n",
    "                cnt+=i-bisect_left(nums,num-dist,0,i)\n",
    "            return cnt>=k\n",
    "\n",
    "        left,right=0,nums[-1]-nums[0]\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid:int) ->int:\n",
    "            cnt =0\n",
    "            i=0\n",
    "            for j,num in enumerate(nums):\n",
    "                while num - nums[i]>mid:\n",
    "                    i+=1\n",
    "                cnt +=j-i\n",
    "            return cnt\n",
    "        nums.sort()\n",
    "        \n",
    "        left =0\n",
    "        right = nums[-1]-nums[0]\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if count(mid)>=k:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return right+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l=0\n",
    "        n=len(nums)\n",
    "        r=nums[-1]-nums[0]\n",
    "        def check(value):\n",
    "            index=0\n",
    "            num=0\n",
    "            maxvalue=0\n",
    "            for i in range(1,n):\n",
    "                while nums[i]-nums[index]>value:\n",
    "                    index+=1\n",
    "                num+=i-index\n",
    "                maxvalue=max(maxvalue,nums[i]-nums[index])\n",
    "            return num, maxvalue\n",
    "        while l<=r:\n",
    "            \n",
    "            m=(l+r)//2\n",
    "            a,b=check(m)\n",
    "            if a>k:\n",
    "                r=m-1\n",
    "            if a==k:\n",
    "                return b\n",
    "            if a<k:\n",
    "                l=m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 有序数组方便进行二分查找\n",
    "        # 由于第k小的数对距离必然在区间【l=0，r=max(nums)-min(nums)】,因此在此区间进行二分\n",
    "        distance_pair_list = range(0, nums[-1] - nums[0] + 1)  # 索引和值等同\n",
    "\n",
    "        def count(dis):  # 计算所有距离小于等于dis的数对数目number\n",
    "            number = 0\n",
    "            # 此时数组有序，nums[i]：较小值 <= dis <= nums[j]：较大值，其中【0 <= i < j <= len(nums)-1】,\n",
    "            # 遍历数组，枚举所有数对的右端点j, 【数对距离小于等于dis】<==>【数组元素大于等于val-dis（即较小值）】的最小值的下标\n",
    "            # 注意每次循环都固定了数对右端点(从数组第二个数开始)，在二分查找时只需向左查找左端点最小值下标，由于切片后val在实际数组中的索引要小一，所以后续需要加一\n",
    "            for j, val in enumerate(nums[1:]):\n",
    "                i = bisect_left(nums, val - dis, 0, j+1)  # j开区间取不到\n",
    "                number += j+1 - i  # 右端点为j且数组元素大于等于val-dis（即较小值）的最小值的下标为i，则共有j-i+1个数对距离小于等于dis\n",
    "            return number\n",
    "\n",
    "        # 将count函数应用于每个数对距离dis（不包含新插入的k），然后将k于转换后的数组进行比较，并没有对数组进行修改\n",
    "        # 如果number > k: r = dis - 1    ->说明比dis小的数对个数已经大于k,需要左移寻找更小的数对\n",
    "        # 如果number = k: r = dis - 1    ->说明比dis小的数对个数就等于k,需要只需r左移退出循环即可\n",
    "        # 如果number < k: l = dis + 1     ->说明比dis小的数对个数小于k,需要右移寻找更大的数对\n",
    "        # 当l > r时二分查找结束，则第k小的数对距离为l（由于索引和值等同，索引l即为数对距离）\n",
    "        return bisect_left(distance_pair_list, k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        def count(d):\n",
    "            count = 0\n",
    "            for i in range(len(nums)):\n",
    "                j = bisect_left(nums, nums[i] - d, 0, i)\n",
    "                count += i - j\n",
    "            return count\n",
    "        \n",
    "        ans = bisect_left(range(nums[-1] - nums[0]), k, key=count)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        dist = nums[-1] - nums[0]\n",
    "\n",
    "        def count(d):\n",
    "            total = 0\n",
    "            j = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                while nums[j] < num - d:\n",
    "                    j += 1\n",
    "                total += i - j\n",
    "            return total\n",
    "        \n",
    "        ans = bisect.bisect_left(range(dist), k, key=count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        l = 0\n",
    "        r = max(nums) - min(nums)\n",
    "        while l <= r:\n",
    "            mid = l + (r-l)//2\n",
    "            # 单调性：mid越小，小于mid的数对差越少，此题求的是第k小的数对，如果此时小于mid的数对已经小于k，就应该让mid取更大值，因此去右侧二分，如果此时小于mid的数对已经大于k，说明mid太大，可以去左侧二分\n",
    "            if self.f(nums, mid) >= k:\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans\n",
    "\n",
    "    def f(self, nums, mid):  # 数对差小于等于mid的有几对\n",
    "        r = 0\n",
    "        ans = 0\n",
    "        for l in range(len(nums)-1):\n",
    "            while r+1 <= len(nums)-1 and nums[r+1] - nums[l] <= mid:\n",
    "                r += 1\n",
    "            ans += r - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        def countsum(mid):\n",
    "            count = i = 0\n",
    "            for j, item in enumerate(nums):\n",
    "                i = bisect_left(nums, item - mid, 0, j)\n",
    "                count += j - i\n",
    "            return count\n",
    "        ans = bisect_left(range(nums[-1]-nums[0]), k, key=countsum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        dist = nums[-1] - nums[0]\n",
    "\n",
    "        def count(d):\n",
    "            total = 0\n",
    "            j = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                while nums[j] < num - d:\n",
    "                    j += 1\n",
    "                total += i - j\n",
    "            return total\n",
    "        \n",
    "        ans = bisect.bisect_left(range(dist), k, key=count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        dist = nums[-1] - nums[0]\n",
    "\n",
    "        @cache\n",
    "        def count(d):\n",
    "            total = 0\n",
    "            j = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                while nums[j] < num - d:\n",
    "                    j += 1\n",
    "                total += i - j\n",
    "            return total\n",
    "        \n",
    "        ans = bisect.bisect_left(range(dist), k, key=count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        heap = []\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            heapq.heappush(heap, (abs(nums[i] - nums[i+1]), i, i+1))\n",
    "        \n",
    "        while k:\n",
    "            distance, i, j = heapq.heappop(heap)\n",
    "            if j+1<n:\n",
    "                heapq.heappush(heap, (abs(nums[i] - nums[j+1]), i, j+1))\n",
    "            k-=1\n",
    "        \n",
    "        return distance\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        def count_pairs(mid):\n",
    "            count=0\n",
    "            j=0\n",
    "            for i in range(n):\n",
    "                while j<n and nums[j]-nums[i]<=mid:\n",
    "                    j+=1\n",
    "                count+=j-i-1\n",
    "            return count\n",
    "\n",
    "        left,right=0,nums[-1]-nums[0]\n",
    "        while left<right:\n",
    "            mid=(right+left)//2\n",
    "            if count_pairs(mid)<k:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def f(nums,limit,n):            \n",
    "            cnt=0\n",
    "            r=1\n",
    "            for l in range(n-1):\n",
    "                while r<n and nums[r]-nums[l]<=limit:\n",
    "                    r+=1\n",
    "                cnt+=r-l-1\n",
    "            return cnt            \n",
    "                                \n",
    "        nums.sort()         \n",
    "        n=len(nums)   \n",
    "        l=0\n",
    "        r=nums[-1]-nums[0]       \n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            cnt=f(nums,mid,n)\n",
    "            if cnt>=k:\n",
    "                res=mid\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            j = 0\n",
    "            for i in range(len(nums)):\n",
    "                while j < len(nums) and nums[j] - nums[i] <= mid:\n",
    "                    j += 1\n",
    "                cnt += j - i - 1\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        # 使用二分查找找到满足 count(mid) >= k 的最小的 mid 值\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def countDistancePair(nums, mid):\n",
    "            n = len(nums)\n",
    "            count = 0\n",
    "            left, right = 0, 0\n",
    "            for right in range(n):\n",
    "                while abs(nums[left]-nums[right]) > mid:\n",
    "                    left += 1\n",
    "                count += right - left\n",
    "            return count\n",
    "        \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left, right = 0, nums[n - 1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            if countDistancePair(nums, mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: list[int], k: int) -> int:\n",
    "        def count(distance):\n",
    "            sum_ = 0\n",
    "            for right in range(1, len(nums)):\n",
    "                lo_ = 0\n",
    "                hi_ = right\n",
    "                while lo_ < hi_:\n",
    "                    mid_ = lo_ + hi_ >> 1\n",
    "                    if nums[right] - nums[mid_] <= distance:\n",
    "                        hi_ = mid_\n",
    "                    else:\n",
    "                        lo_ = mid_ + 1\n",
    "                sum_ += (right - lo_)\n",
    "            return sum_\n",
    "\n",
    "        nums.sort()\n",
    "        lo = 0\n",
    "        hi = nums[-1] - nums[0]\n",
    "        while lo < hi:\n",
    "            mid = lo + hi >> 1\n",
    "            if count(mid) >= k:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 有序数组方便进行二分查找\n",
    "        # 由于第k小的数对距离必然在区间【l=0，r=max(nums)-min(nums)】,因此在此区间进行二分\n",
    "        distance_pair_list = range(0, nums[-1] - nums[0] + 1)  # 索引和值等同\n",
    "\n",
    "        def count(dis):  # 计算所有距离小于等于dis的数对数目number\n",
    "            number = i = 0\n",
    "            # 此时数组有序，nums[i]：较小值 <= dis <= nums[j]：较大值，其中【0 <= i < j <= len(nums)-1】,\n",
    "            # 遍历数组，枚举所有数对的右端点j, 【数对距离小于等于dis】<==>【数组元素大于等于val-dis（即较小值）】的最小值的下标\n",
    "            # 注意每次循环都固定了数对右端点(从数组第二个数开始)，在二分查找时只需向左查找左端点最小值下标，由于切片后val在实际数组中的索引要小一，所以后续需要加一\n",
    "            for j, val in enumerate(nums[1:]):\n",
    "                while nums[i] < val - dis:  # 当数组元素大于等于val-dis（即较小值）退出循环，此时i即为数组元素大于等于val-dis（即较小值）的最小值的下标\n",
    "                    i += 1\n",
    "                number += j + 1 - i  # 右端点为j+1且最小值的下标为i，则共有j+1-i个数对距离小于等于dis\n",
    "            return number\n",
    "\n",
    "        # 将count函数应用于每个数对距离dis（不包含新插入的k），然后将k于转换后的数组进行比较，并没有对数组进行修改\n",
    "        # 如果number > k: r = dis - 1    ->说明比dis小的数对个数已经大于k,需要左移寻找更小的数对\n",
    "        # 如果number = k: r = dis - 1    ->说明比dis小的数对个数就等于k,需要只需r左移退出循环即可\n",
    "        # 如果number < k: l = dis + 1     ->说明比dis小的数对个数小于k,需要右移寻找更大的数对\n",
    "        # 当l > r时二分查找结束，则第k小的数对距离为l（由于索引和值等同，索引l即为数对距离）\n",
    "        return bisect_left(distance_pair_list, k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        left = 0\n",
    "        right = nums[-1] - nums[0]\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            l = 0\n",
    "            cnt = 0\n",
    "            for r, num in enumerate(nums):\n",
    "                while num - nums[l] > mid:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "\n",
    "            if cnt >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        # 二分的精髓就在于不要看他们给定的数组的值，而是要在一个范围内找到mid，然后看mid是否符合要求，\n",
    "        # 然后找到不变量\n",
    "        # 这里更多一层的是决定了mid之后，还要在一定的范围内看符合要求的数达到k的要求了吗\n",
    "\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        # left 代表最小的绝对差值0，right代表最大的绝对差值\n",
    "        # 如果他们的中间值mid，遍历整个数组得到的比mid小的绝对差值超过k个了，那就代表mid大了，right更新\n",
    "        # 反之left更新。\n",
    "        # 那么不变量是什么，\n",
    "        left, right = 0, nums[-1] - nums[0] # 开区间\n",
    "        \n",
    "        def get_count(mid) -> int:\n",
    "            # 计算小于等于mid的绝对差值有多少个，如果大于k个，那么就代表mid太大了，right更新\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > mid:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "\n",
    "        # 开始二分\n",
    "        while left <= right:\n",
    "            mid = (right + left) // 2\n",
    "            if get_count(mid) < k:\n",
    "                # 绝对差值大于mid的没有k个\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        def cnt(n):\n",
    "            res = 0\n",
    "            i = 0\n",
    "            for j in range(1, len(nums)):\n",
    "                while nums[j]-nums[i]>n:\n",
    "                    i += 1\n",
    "\n",
    "                res += j-i\n",
    "            \n",
    "            return res\n",
    "\n",
    "        l = 0\n",
    "        r = nums[-1]-nums[0]\n",
    "        while l<r:\n",
    "            x = (l+r)//2\n",
    "            if cnt(x)<k:\n",
    "                l = x+1\n",
    "            else:\n",
    "                r = x\n",
    "\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def check(x):\n",
    "            c = 0\n",
    "            pos = 0\n",
    "            for i in range(len(nums) - 1):\n",
    "                while pos < len(nums) and nums[pos] - nums[i] <= x:\n",
    "                    pos += 1\n",
    "                c += pos - i - 1\n",
    "            return c\n",
    "\n",
    "        nums.sort()\n",
    "        l, r = -1, nums[-1] - nums[0] + 1\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            # print(m, check(m))\n",
    "            if check(m) >= k: r = m\n",
    "            else: l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        def check(mid):\n",
    "            que=deque()\n",
    "            cnt=0\n",
    "            for i in nums:\n",
    "                while que and i-que[0]>mid:\n",
    "                    que.popleft()\n",
    "                cnt+=len(que)\n",
    "                que.append(i)\n",
    "                if cnt>=k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        l=-1\n",
    "        r=max(nums)-min(nums)+1\n",
    "        while l+1!=r:\n",
    "            mid=(l+r)//2\n",
    "            #print(mid,check(mid))\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 有序方便进行二分查找\n",
    "        # 由于第k小的数对距离必然在区间【l=0，r=max(nums)-min(nums)】,在此区间进行二分\n",
    "        distance_pair_list = range(nums[-1] - nums[0]+1)\n",
    "\n",
    "        def count(dis):  # 计算所有距离小于等于mid的数对数目\n",
    "            number = 0\n",
    "            for sub, val in enumerate(nums):\n",
    "                index = bisect_left(nums, val-dis, 0, sub)\n",
    "                number += sub - index\n",
    "            return number\n",
    "\n",
    "        # 将count函数应用于每个数对距离dis，返回所有小于等于dis的数对数目number\n",
    "        # 如果number>=k: r = mid - 1, 否则l = mid + 1\n",
    "        # 当l>r时二分查找结束，则第k小的数对距离为l\n",
    "        return bisect_left(distance_pair_list, k, key=count)\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: list[int], k: int) -> int:\n",
    "        def count(distance):\n",
    "            sum_ = 0\n",
    "            for right in range(1, len(nums)):\n",
    "                lo_ = 0\n",
    "                hi_ = right\n",
    "                while lo_ < hi_:\n",
    "                    mid_ = lo_ + hi_ >> 1\n",
    "                    if nums[right] - nums[mid_] <= distance:\n",
    "                        hi_ = mid_\n",
    "                    else:\n",
    "                        lo_ = mid_ + 1\n",
    "                sum_ += (right - lo_)\n",
    "            return sum_\n",
    "\n",
    "        nums.sort()\n",
    "        lo = 0\n",
    "        hi = nums[-1] - nums[0]\n",
    "        while lo < hi:\n",
    "            mid = lo + hi >> 1\n",
    "            if count(mid) >= k:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid):\n",
    "            cnt, i = 0, 0\n",
    "            for j in range(len(nums)):\n",
    "                while nums[j]-nums[i] > mid:\n",
    "                    i += 1\n",
    "                cnt += j-i\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        return bisect_left(range(nums[-1]-nums[0]), k, key=count)\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            j = 0\n",
    "            for i in range(len(nums)):\n",
    "                while j < len(nums) and nums[j] - nums[i] <= mid:\n",
    "                    j += 1\n",
    "                cnt += j - i - 1\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        # 使用二分查找找到满足 count(mid) >= k 的最小的 mid 值\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def get_count(dis):\n",
    "            cnt = l = 0\n",
    "            for r in range(len(nums)):\n",
    "                while nums[r] - nums[l] > dis:\n",
    "                    l += 1\n",
    "                cnt += r - l\n",
    "            return cnt\n",
    "        \n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if get_count(mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid):\n",
    "            cnt = 0\n",
    "            i, j = 0, 1\n",
    "            n = len(nums)\n",
    "            while i < n:\n",
    "                while j < n and nums[j]-nums[i] <= mid:\n",
    "                    j += 1\n",
    "                cnt += j-i-1\n",
    "                i += 1\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        # print (count(4))\n",
    "        # 0..8\n",
    "        return bisect.bisect_left(range(nums[-1]-nums[0]), k, key=count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            for j, num in enumerate(nums):\n",
    "                i = bisect_left(nums, num - mid, 0, j)\n",
    "                cnt += j - i\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        return bisect_left(range(nums[-1] - nums[0]), k, key=count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def countDistancePair(nums, mid):\n",
    "            n = len(nums)\n",
    "            count = 0\n",
    "            left, right = 0, 0\n",
    "            for right in range(n):\n",
    "                while abs(nums[left]-nums[right]) > mid:\n",
    "                    left += 1\n",
    "                count += right - left\n",
    "            return count\n",
    "        \n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        left, right = 0, nums[n - 1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            if countDistancePair(nums, mid) < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def check(distance):\n",
    "            cnt = 0\n",
    "            j = 1\n",
    "            for i in range(len(nums)):\n",
    "                while j<len(nums) and nums[j]-nums[i]<=distance:\n",
    "                    j+=1\n",
    "                cnt += j-i-1\n",
    "                if cnt>=k:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        nums.sort()\n",
    "        l,r = 0,10**6\n",
    "        while l<r:\n",
    "            mid = l+(r-l)//2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        def count(mid: int) -> int:\n",
    "            cnt = 0\n",
    "            for j, num in enumerate(nums):\n",
    "                i = bisect_left(nums, num - mid, 0, j)\n",
    "                cnt += j - i\n",
    "            return cnt\n",
    "\n",
    "        nums.sort()\n",
    "        return bisect_left(range(nums[-1] - nums[0]), k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        r = nums[-1]-nums[0]+1\n",
    "        l = min([nums[i]-nums[i-1] for i in range(1,N)])\n",
    "        def count(m):\n",
    "            cnt = 0\n",
    "            h = N-2\n",
    "            for i in range(N-1,0,-1):\n",
    "                num = nums[i]\n",
    "                idx = bisect.bisect_left(nums,num-m,hi=h+1)\n",
    "                # print(nu)\n",
    "                cnt+=i-idx\n",
    "                if cnt>k:\n",
    "                    break\n",
    "                h = idx\n",
    "            # print(m,cnt)\n",
    "            return cnt \n",
    "\n",
    "        return l+bisect_left(range(l,r),k,key=count)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def get_cnt(target):\n",
    "            res = 0\n",
    "            l = 0\n",
    "            for r in range(n):\n",
    "                while l < r and nums[r] - nums[l] > target:\n",
    "                    l += 1\n",
    "                res += r - l\n",
    "            return res\n",
    "\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = nums[-1] - nums[0]\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            cnt = get_cnt(mid)\n",
    "            if cnt < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 有序数组方便进行二分查找\n",
    "        # 由于第k小的数对距离必然在区间【l=0，r=max(nums)-min(nums)】,因此在此区间进行二分\n",
    "        distance_pair_list = range(0, nums[-1] - nums[0] + 1)  # 索引和值等同\n",
    "\n",
    "        def count(dis):  # 计算所有距离小于等于dis的数对数目number\n",
    "            number = 0\n",
    "            # 此时数组有序，nums[i]：较小值 <= dis <= nums[j]：较大值，其中【0 <= i < j <= len(nums)-1】,\n",
    "            # 遍历数组，枚举所有数对的右端点j, 【数对距离小于等于dis】<==>【数组元素大于等于val-dis（即较小值）】的最小值的下标\n",
    "            # 注意每次循环都固定了数对右端点(从数组第二个数开始)，在二分查找时只需向左查找左端点最小值下标，由于切片后val在实际数组中的索引要小一，所以后续需要加一\n",
    "            for j, val in enumerate(nums[1:]):\n",
    "                i = bisect_left(nums, val - dis, 0, j+1)  # j开区间取不到\n",
    "                number += j+1 - i  # 右端点为j且数组元素大于等于val-dis（即较小值）的最小值的下标为i，则共有j-i+1个数对距离小于等于dis\n",
    "            return number\n",
    "\n",
    "        # 将count函数应用于每个数对距离dis（不包含新插入的k），然后将k于转换后的数组进行比较，并没有对数组进行修改\n",
    "        # 如果number > k: r = dis - 1    ->说明比dis小的数对个数已经大于k,需要左移寻找更小的数对\n",
    "        # 如果number = k: r = dis - 1    ->说明比dis小的数对个数就等于k,需要只需r左移退出循环即可\n",
    "        # 如果number < k: l = dis + 1     ->说明比dis小的数对个数小于k,需要右移寻找更大的数对\n",
    "        # 当l > r时二分查找结束，则第k小的数对距离为l（由于索引和值等同，索引l即为数对距离）\n",
    "        return bisect_left(distance_pair_list, k, key=count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\r\n",
    "        nums=sorted(nums)\r\n",
    "        def f(m):\r\n",
    "            ans=0\r\n",
    "            i=0\r\n",
    "            j=1\r\n",
    "            while j!=len(nums)-1:\r\n",
    "                if nums[j]-nums[i]<=m:\r\n",
    "                    j+=1\r\n",
    "                    continue\r\n",
    "                if nums[j]-nums[i]>m:\r\n",
    "                    ans+=j-i-1\r\n",
    "                    i+=1\r\n",
    "                    continue\r\n",
    "            if nums[j]-nums[i]<=m:\r\n",
    "                    ans+=(j-i)*(j-i+1)//2\r\n",
    "                    return ans\r\n",
    "            if nums[j]-nums[i]>m:\r\n",
    "                    ans+=(j-i-1)*(j-i)//2\r\n",
    "            while i<j:\r\n",
    "                i+=1\r\n",
    "                if nums[j]-nums[i]<=m:\r\n",
    "                    ans+=j-i\r\n",
    "                    break\r\n",
    "            return ans\r\n",
    "        l=0\r\n",
    "        r=1e6\r\n",
    "        while l<r:\r\n",
    "            mid=(l+r)//2\r\n",
    "            tmp=f(mid)\r\n",
    "            if tmp<k:\r\n",
    "                l=mid+1\r\n",
    "            else:\r\n",
    "                r=mid\r\n",
    "        return int(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            count = 0\n",
    "            j = 0\n",
    "            for i in range(len(nums)):\n",
    "                while j < len(nums) and nums[j] - nums[i] <= mid:\n",
    "                    j += 1\n",
    "                count += j - i - 1\n",
    "            if count < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l, r = 0, int(1e6)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if self.check(nums, mid, k):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r\n",
    "\n",
    "    def check(self, nums, x, k):\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        j = 1\n",
    "        for i in range(n):\n",
    "            while j < n and nums[j] - nums[i] <= x:\n",
    "                j += 1\n",
    "            ans += j - i - 1\n",
    "            if ans >= k:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            for i in range(1, len(nums)):\n",
    "                idx1 = bisect_left(nums, nums[i] - num, 0, i)\n",
    "                cnt += i - idx1\n",
    "            return cnt >= k\n",
    "\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        r = nums[-1] - nums[0]\n",
    "        if l == r:\n",
    "            return 0\n",
    "        while l < r:\n",
    "            if l + 1 == r:\n",
    "                if check(l):\n",
    "                    return l\n",
    "                else:\n",
    "                    return r\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return -1\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.smallestDistancePair(nums=[1, 3, 1], k=1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left, right = 0, nums[-1] - nums[0]\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            count, j = 0, 0\n",
    "            for i in range(len(nums)):\n",
    "                while j < len(nums) and nums[j] - nums[i] <= mid:\n",
    "                    j += 1\n",
    "                count += j - i - 1\n",
    "            if count < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDistancePair(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()  # 有序数组方便进行二分查找\n",
    "        # 由于第k小的数对距离必然在区间【l=0，r=max(nums)-min(nums)】,因此在此区间进行二分\n",
    "        distance_pair_list = range(0, nums[-1] - nums[0] + 1)  # 索引和值等同\n",
    "\n",
    "        def count(dis):  # 计算所有距离小于等于dis的数对数目number\n",
    "            number = 0\n",
    "            # 此时数组有序，nums[i]：较小值 <= dis <= nums[j]：较大值，其中【0 <= i < j <= len(nums)-1】,\n",
    "            # 遍历数组，枚举所有数对的右端点j, 【数对距离小于等于dis】<==>【数组元素大于等于val-dis（即较小值）】的最小值的下标\n",
    "            # 注意每次循环都固定了数对右端点，在二分查找时只需向左查找左端点最小值下标\n",
    "            for j, val in enumerate(nums[1:]):\n",
    "                i = bisect_left(nums, val - dis, 0, j+1)\n",
    "                number += j+1 - i  # 右端点为j且数组元素大于等于val-dis（即较小值）的最小值的下标为i，则共有j-i个数对距离小于等于dis\n",
    "            return number\n",
    "\n",
    "        # 将count函数应用于每个数对距离dis（不包含新插入的k），然后将k于转换后的数组进行比较，并没有对数组进行修改\n",
    "        # 如果number > k: r = dis - 1    ->说明比dis小的数对个数已经大于k,需要左移寻找更小的数对\n",
    "        # 如果number = k: r = dis - 1    ->说明比dis小的数对个数就等于k,需要只需r左移退出循环即可\n",
    "        # 如果number < k: l = dis + 1     ->说明比dis小的数对个数小于k,需要右移寻找更大的数对\n",
    "        # 当l > r时二分查找结束，则第k小的数对距离为l（由于索引和值等同，索引l即为数对距离）\n",
    "        return bisect_left(distance_pair_list, k, key=count)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
